package 二叉树;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author XZ
 * @create 2021-10-17 21:31
 * https://leetcode-cn.com/problems/binary-tree-inorder-traversal/submissions/
 */
public class _94_二叉树的中序遍历 {
    //方式一：递归
    public List<Integer> inorderTraversal1(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        inOrderTraversal(root,list);
        return list;
    }
    private void inOrderTraversal(TreeNode node, List list) {
        if (node == null) {
            return;
        }
        inOrderTraversal(node.left,list);
        list.add(node.val);
        inOrderTraversal(node.right,list);
    }

    //方式二：遍历，不是自己写的
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {
                root = stack.pop();
                list.add(root.val);
                root = root.right;
            }
        }
        return list;
    }
}